package leetcode.p1504;

import java.util.Stack;

/**
 * @author: trtan
 * @date: 2021-06-15 10:40
 **/
public class CountSubWithAllOnes {
    public int numSubmat(int[][] mat) {
        if (mat.length == 0 || mat[0].length == 0) {
            return 0;
        }
        int n = mat.length;
        int m = mat[0].length;
        //对每个点记录往左能有多少个1（包含自己）
        int[][] pre = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    pre[i][j] = 0;
                } else {
                    if (j == 0) {
                        pre[i][j] = 1;
                    } else {
                        pre[i][j] = pre[i][j - 1] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(pre[i][j] + ", ");
            }
            System.out.println();
        }
        int result = 1;
        //按照从上往下从左往右的方式遍历
        // 对于每个(i，j)作为右下角，都可以前i-1个前缀和（pre）计算得到
        for (int j = 0; j < m; j++) {
            // 单调栈维护前i-1个的前缀和 维护单调递增栈
            Stack<int[]> sta = new Stack<>();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                // 记录数量，因为弹出后 后面再次弹出时需要计算到
                int count = 0;
                while (!sta.isEmpty() && pre[i][j] < sta.peek()[0]) {
                    int[] top = sta.pop();
                    sum -= (top[0] - pre[i][j]) * top[1];
                    count += top[1];
                }
                sum += pre[i][j];
                sta.push(new int[] {pre[i][j], count});
                result += sum;
            }
        }
        return result;
    }
}
